I might suggest doing something along the lines of a breadth-first search from the start to the end: Determine connecting faces (maybe even a bit each for "clockwise of middle" and "counterclockwise of middle" doors, so an L-shaped tile in "L" orientation would have a "counterclockwise of middle" connection upwards and a "clockwise of middle" connection right) of each tile. Initialize your grid, considering empty squares fully-connected (excluding those connections on the edges of the map). For each square, mark each of its connections as a path to the end. From here on out, you'll be placing tiles. Each time you place a tile, update the square's connection info and visit each neighboring square. Remove any of the neighbor's connections which don't match the placed tile, and unmark the matching connections as possible paths to the end. If this leaves the neighbor without any connections marked as paths to the end, visit each of the neighbor's neighbors and unmark their matching connections as possible paths to the end; recurse as necessary (note, you only need to recurse if some connection's mark was removed; spaces which were already unconnected need no further work). Place your start and end tiles, updating the connection info of the relevant grid spaces (at this point you know that there's a possible path from start to end, because every other space is a fully-connected empty space). Place random tiles adjacent to each connection. Restrict your random options to those tiles with matching connections, and only those tiles which maintain at least one potential path from start to end. Update the connection info for the relevant spaces. Repeat the previous step until no connections remain. Possibly something like this (untested, so probably not quite right): CONNECTION_UL = (1<<0); //numbered around the circle so that geometric rotation can be done by bitwise rotation
CONNECTION_UR = (1<<1);
CONNECTION_RU = (1<<2);
CONNECTION_RD = (1<<3);
CONNECTION_DR = (1<<4);
CONNECTION_DL = (1<<5);
CONNECTION_LD = (1<<6);
CONNECTION_LU = (1<<7);
MASK_U = CONNECTION_UL | CONNECTION_UR;
MASK_R = CONNECTION_RU | CONNECTION_RD;
MASK_D = CONNECTION_DR | CONNECTION_DL;
MASK_L = CONNECTION_LD | CONNECTION_LU;
ALL_DIRECTIONS = [MASK_U, MASK_R, MASK_D, MASK_L];
TILE_BIG_ROOM = 0xff; //all connection bits, setting by number instead of symbolic constant for brevity
TILE_SMALL_ROOM = CONNECTION_UR | CONNECTION RU; //small room in top right corner
TILE_HALL = CONNECTION_LU | CONNECTION_RU; //hall across top
ALL_TILES = [TILE_BIG_ROOM, TILE_SMALL_ROOM, TILE_HALL];
function rotateClockwise(tile){
return (tile >> 6) | ((tile << 2) & 0xff);
}
function rotateCounterClockwise(tile){
return (tile >> 2) | ((tile << 6) & 0xff);
}
function flip(tile){
return (tile >> 4) | ((tile << 4) & 0xff);
}
function directionCount(c){
return (c & MASK_U ? 1 : 0) + (c & MASK_R ? 1 : 0) + (c & MASK_D ? 1 : 0) + (c & MASK_L ? 1 : 0);
}
var grid = [];
var squaresToFill = [];
var startPoint = [];
var endPoint = [];
function initGrid(w, h){
for (var i = 0; i < w; i++){
grid[i] = [];
for (var j = 0; j < h; j++){
connections = 0;
if (i > 0){ connections |= CONNECTION_LU | CONNECTION_LD; }
if (i < w - 1){ connections |= CONNECTION_RU | CONNECTION_RD; }
if (j > 0){ connections |= CONNECTION_UL | CONNECTION_UR; }
if (j < h - 1){ connections |=CONNECTION_DL | CONNECTION_DR; }
grid[i][j] = {'connections': connections, 'paths': connections, 'filled': 0};
}
}
}
function addSquareToFill(x, y, requiredConnections){
if ((x < 0) || (x >= grid.length) || (y < 0) || (y >= grid[x].length)){ return; } //square outside of grid
if (grid[x][y].filled){ return; } //square already filled
for (var i = 0; i < squaresToFill.length; i++){
if ((squaresToFill[i][0] == x) && (squaresToFill[i][1] == y)){
squaresToFill[i][2] |= requiredConnections;
return;
}
}
squaresToFill.push([x, y, requiredConnections]);
}
function updateUnplaced(x, y, connections, mask){
if ((x < 0) || (x >= grid.length) || (y < 0) || (y >= grid[x].length)){ return; } //square outside of grid
if (grid[x][y].filled){ return; } //tile already placed, no more work to do here
if (!(grid[x][y].paths & mask)){ return; } //square doesn't depend on connections from this direction
var invMask = ~mask & 0xff;
grid[x][y].connections &= (connections | invMask);
grid[x][y].paths &= invMask;
if (directionCount(grid[x][y].paths) > 1){ return; } //square still connected in multiple other directions
var flippedConnections = flip(grid[x][y].connections);
updateUnplaced(x - 1, y, flippedConnections, MASK_R);
updateUnplaced(x + 1, y, flippedConnections, MASK_L);
updateUnplaced(x, y - 1, flippedConnections, MASK_D);
updateUnplaced(x, y + 1, flippedConnections, MASK_U);
}
function placeTile(tile, x, y){
grid[x][y].filled = 1;
grid[x][y].connections &= tile;
grid[x][y].paths = 0;
var flippedConnections = flip(grid[x][y].connections);
if (grid[x][y].connections & MASK_L){ addSquareToFill(x - 1, y, flippedConnections & MASK_R); }
if (grid[x][y].connections & MASK_R){ addSquareToFill(x + 1, y, flippedConnections & MASK_L); }
if (grid[x][y].connections & MASK_U){ addSquareToFill(x, y - 1, flippedConnections & MASK_D); }
if (grid[x][y].connections & MASK_D){ addSquareToFill(x, y + 1, flippedConnections & MASK_U); }
updateUnplaced(x - 1, y, flippedConnections, MASK_R);
updateUnplaced(x + 1, y, flippedConnections, MASK_L);
updateUnplaced(x, y - 1, flippedConnections, MASK_D);
updateUnplaced(x, y + 1, flippedConnections, MASK_U);
}
function placeEndpoints(){
startPoint = [randomInteger(grid.length) - 1, randomInteger(grid[0].length) - 1];
endPoint = [randomInteger(grid.length) - 1, randomInteger(grid[0].length) - 1];
placeTile(TILE_BIG_ROOM, startPoint[0], startPoint[1]);
placeTile(TILE_BIG_ROOM, endPoint[0], endPoint[1]);
}
function candidateValid(candidate, requiredConnections, outboundPaths){
var overlap = candidate & requiredConnections
for (var mask in ALL_DIRECTIONS){
if ((requiredConnections & mask) && !(overlap & mask)){
return 0; //candidate doesn't make a required connection
}
} //candidate makes all required connections
if (!outboundPaths){ return 1; } //no outbound paths are necessary, so candidate is valid
return candidate & outboundPaths; //valid iff candidate matches at least one outboundPath
}
function fillSquare(x, y, requiredConnections){
var outboundPaths = 0;
if ((x > 0) && (!grid[x-1][y].filled) && (grid[x-1][y].paths)){ outboundPaths |= MASK_L; }
if ((x < grid.length - 1) && (!grid[x+1][y].filled) && (grid[x+1][y].paths)){ outboundPaths |= MASK_R; }
if ((y > 0) && (!grid[x][y-1].filled) && (grid[x][y-1].paths)){ outboundPaths |= MASK_U; }
if ((y > grid[x].length - 1) && (!grid[x][y+1].filled) && (grid[x][y+1].paths)){ outboundPaths |= MASK_D; }
for (var i = 0; i < squaresToFill.length; i++){
if (grid[squaresToFill[i][0]][squaresToFill[i][1]].paths){
outboundPaths = 0;
break;
}
}
var candidates = [];
for (var i = 0; i < ALL_TILES.length; i++){
var candidate = ALL_TILES[i];
for (var j = 0; j < 4; j++){
if (candidateValid(candidate, requiredConnections, outboundPaths)){
candidates.push(candidate);
}
candidate = rotateClockwise(candidate);
}
}
var tileIndex = randomInteger(candidates.length) - 1;
placeTile(candidates[tileIndex], x, y);
}
function fillTiles(){
while (squaresToFill.length > 0){
square = squaresToFill.shift();
fillSquare(square[0], square[1], square[2]);
}
}
/////
//
// main entry point: generateMap(width, height)
//
/////
function generateMap(w, h){
grid = []; //re-initialize globals in case this gets called multiple times
squaresToFill = [];
startPoint = [];
endPoint = [];
initGrid(w, h);
placeEndpoints();
fillTiles();
} Grr markdown. There went all my formatting...
